package com.nanbei.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @ClassDescription: 快速排序 (随即基准点) 在排序的数组中包含重复元素
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/6/26 17:02
 */
public class QuickSortRandom {

    public static void main(String[] args) {
        int[] ints = {6,1,11,32, 4, 3,5,6,7,3,6,9,6 };
        int[] bubbling = QuickSortRandom.selection(ints);
        System.out.println(Arrays.toString(bubbling));
    }


    public static int[] selection(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = querySort(nums, left, right);
        sort(nums, left, i - 1);
        sort(nums, i + 1, right);
    }

    /**
     *
     * - 选择随机下标元素作为基准点 ， 然后交换最左侧元素和随机下标的基准点元素
     * 选择基准点：通常选择数组的第一个元素（最左侧元素）作为基准点。
     * 从左到右查找：从数组的左侧开始查找，直到找到一个大于、等于基准点的元素。
     * 从右到左查找：从数组的右侧开始查找，直到找到一个小、等于于基准点的元素。
     * 如果min <= max 则交换上面查找到的两个元素
     * 交换完成成后 min++ ,max-- 在重复上述的步骤
     *
     * 最后需要交换 left  max 下标的元素（为什么是max？）
     * 交换后max-- min++ max会被交换到min的左侧
     *
     * nums[left] 为基准点时需要先 从右向左找小的、在从左向右找大的
     * nums[right] 为基准点时需要先 从左向右找大的、从右向左找小的
     *
     * @param nums  数组
     * @param left  左边界
     * @param right 右边界
     * @return 基点下标
     */
    private static int querySort(int[] nums, int left, int right) {
        Random random = new Random();
        // 生成一个随机数下标，将下标元素作为基准点元素
        int nextInt = random.nextInt(right - left + 1);
        int index = nextInt + left;
        // 交换随机的基准坐标和最左侧的元素
        swap(nums,index,left);

        int max = right;
        int min = left+1;
        int pv = nums[left];
        while (min <= max) {

            // 从右向左找 小于等于 基准点的
            while (min <= max && nums[max] > pv) {
                max--;
            }

            // 从左向右找 大于等于 基准点的
            while (min <= max && nums[min] < pv) {
                min++;
            }

            // 找到后交换位置
            if (min <= max){
                swap(nums, max, min);
                min++;
                max--;
            }

        }

        swap(nums, left, max);
        return max;

    }

    public static void swap(int[] nums, int i, int j) {
        Sort.swap(nums, i, j);
    }


}
